/*
 * Copyright (c) 2011-2024, Cpjit (cpjit@qq.com).
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.cpjit.common.collect;

import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.collections4.ListUtils;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;

/**
 * @author yonghuan[cpjit@qq.com]
 */
public final class TreeUtils {

    /**
     * 构建树
     *
     * @param nodes          节点列表
     * @param parentGetter   获取父节点的函数
     * @param childrenGetter 获取子节点的函数
     * @param <T>            节点类型
     * @return 树
     */
    public static <T> List<T> buildTree(List<T> nodes, BiFunction<List<T>, T, T> parentGetter, Function<T, List<T>> childrenGetter) {
        List<T> tree = new ArrayList<>();
        for (T node : nodes) {
            T parent = parentGetter.apply(tree, node);
            if (parent != null) {
                childrenGetter.apply(parent).add(node);
            } else {
                tree.add(node);
            }
        }
        return tree;
    }

    /**
     * 在树中查找节点，使用广度优先遍历
     */
    public static <T> T findOne(List<T> tree,
                                Function<T, List<T>> childrenGetter,
                                Function<T, Boolean> filter) {
        for (T node : tree) {
            if (filter.apply(node)) {
                return node;
            }
        }
        for (T node : tree) {
            List<T> children = childrenGetter.apply(node);
            if (CollectionUtils.isNotEmpty(children)) {
                T result = findOne(children, childrenGetter, filter);
                if (result != null) {
                    return result;
                }
            }
        }
        return null;
    }

    /**
     * 深度优先遍历树
     */
    public static <T> void visit(List<T> tree, Function<T, List<T>> childrenGetter, BiConsumer<T, T> visitor) {
        visit(tree, null, childrenGetter, (node, parent) -> {
            visitor.accept(node, parent);
            return true;
        });
    }

    /**
     * 深度优先遍历树
     */
    public static <T> void visit(List<T> tree, Function<T, List<T>> childrenGetter, BiFunction<T, T, Boolean> visitor) {
        visit(tree, null, childrenGetter, visitor);
    }

    private static <T> void visit(List<T> tree, T parent, Function<T, List<T>> childrenGetter, BiFunction<T, T, Boolean> visitor) {
        for (T node : tree) {
            if (visitor.apply(node, parent)) {
                List<T> children = childrenGetter.apply(node);
                if (CollectionUtils.isNotEmpty(children)) {
                    visit(children, node, childrenGetter, visitor);
                }
            }
        }
    }

    /**
     * 深度优先遍历树，并删除符合过滤条件的节点
     */
    public static <T> void delete(List<T> tree, Function<T, List<T>> childrenGetter, Function<T, Boolean> filter) {
        for (Iterator<T> itr = tree.iterator(); itr.hasNext(); ) {
            T node = itr.next();
            List<T> children = childrenGetter.apply(node);
            if (CollectionUtils.isNotEmpty(children)) {
                delete(children, childrenGetter, filter);
            }
            if (filter.apply(node)) {
                itr.remove();
            }
        }
    }

    /**
     * 获取树中节点的数量
     */
    public static <T> long size(List<T> tree, Function<T, List<T>> childrenGetter) {
        long size = ListUtils.emptyIfNull(tree).size();
        for (T node : tree) {
            size += size(childrenGetter.apply(node), childrenGetter);
        }
        return size;
    }

    private TreeUtils() {
    }
}
